# Adapted from "FOV using recursive shadowcasting" by Bjorn Bergstrom.

# TODO: Use [array('L')] for the grid.
class FieldOfView(object):
    # Multipliers for transforming coordinates to other octants.
    mult = [[1,  0,  0, -1, -1,  0,  0,  1],
            [0,  1, -1,  0,  0, -1,  1,  0],
            [0,  1,  1,  0,  0, -1, -1,  0],
            [1,  0,  0,  1, -1,  0,  0, -1]]

    def __init__(self, size):
        self.__grid = [[0] * size.y for x in xrange(size.x)]
        self.__time = 1

    def contains(self, x, y):
        try:
            return self.__grid[x][y] == self.__time
        except IndexError:
            return False

    def __contains__(self, pos):
        x, y = pos
        return self.contains(x, y)

    def __add(self, cx, cy, row, start, end, radius, xx, xy, yx, yy, blocked):
        if start < end:
            return
        for j in xrange(row, radius + 1):
            dx, dy = -j - 1, -j
            in_blocked = False
            while dx <= 0:
                dx += 1

                # Track the left and right slopes of the current square.
                left_slope, right_slope = ((dx - 0.5) / (dy + 0.5),
                                           (dx + 0.5) / (dy - 0.5))

                if start < right_slope:
                    continue
                elif end > left_slope:
                    break
                else:
                    # Translate the octant coordinates into map coordinates.
                    x, y = cx + dx * xx + dy * xy, cy + dx * yx + dy * yy

                    if dx ** 2 + dy ** 2 < radius ** 2:
                        try:
                            self.__grid[x][y] = self.__time
                        except IndexError:
                            pass

                    if in_blocked:
                        if blocked(x, y):
                            new_start = right_slope
                            continue
                        else:
                            in_blocked = False
                            start = new_start
                    else:
                        if blocked(x, y) and j < radius:
                            # This is a blocking square, start a child scan:
                            in_blocked = True
                            self.__add(cx, cy, j + 1, start, left_slope,
                                       radius, xx, xy, yx, yy, blocked)
                            new_start = right_slope
            if in_blocked:
                break

    def clear(self):
        self.__time += 1

    def add(self, x, y, radius, blocked):
        try:
            self.__grid[x][y] = self.__time
        except IndexError:
            pass
        for oct in xrange(8):
            self.__add(x, y, 1, 1.0, 0.0, radius,
                       self.mult[0][oct], self.mult[1][oct],
                       self.mult[2][oct], self.mult[3][oct], blocked)
